require "suffix_node.rb"

#Riefinisco il confronto fra stringhe in modo che a<=b significhi che a è 
# prefisso di b mentre a>=b che b è prefisso di a
class String
	def <= (o_str)
		rv = super(o_str)
		if(rv)
			rv = self == o_str[0, self.length]
		end
		rv
	end
	
	def >=(o_str)
		o_str <= self
	end
end

# Costruisce il suffix Trie e mantiene il riferimento alle stringe passate
class SuffixTrie
	attr_accessor :dominio, :root
		def initialize() 
			@dominio = Array.new
			@root = SuffixNode.new(SuffixNodeKey.new, Array.new)
		end
		
#Estrae da @dominio il pezzo di stringa cui nodo si riferisce
	public
		def pezzo(nodo)
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo #{nodo.class}"
			end
			
			str = @dominio[nodo.chiave.indice]
			
			str[nodo.chiave.inizio, nodo.chiave.lunghezza]
			
		end
 
# Ricerca un pattern all'interno del trie
# bold:Argomenti: 
# * italic:pattern è una stringa 
# * italic:node è la radice del trie da cui voglio iniziare la ricerca 
# bold:Ritorna:
# italic:nil se non ha trovato nulla
# italicSuffixNode il nodo che ha trovato
		public
		def search(apattern, node = @root)
			if(!node.is_a?(SuffixNode))
				raise ArgumentError.new("Te 2nd argument #{node.class} " <<\
															"is not a SuffixNode")
			end
			if(!apattern.respond_to?(:to_str))
				raise ArgumentError.new("Te 2nd argument #{pattern.class} " <<\
															"is not a String")
			end
			pattern = apattern.to_str
			#Se non ci sono stringe torna nil... Non ho trovato nulla dopo tutto ;)
			if(@dominio.empty?) 
				nil
			end
			
			m = pattern.size
			i = 0
			u = node
			while (i < m) do
				i_curr = i
				#Vedo se ci sono figli che fanno match con pattern
				u = figlio(u, pattern[i])
				if(u.nil?)
					break
				else
					#Ottengo il tratto di stringa cui u si riferisce
					s = pezzo(u)
					fine = false
					s.each_byte do |c| 
						if(c == pattern[i] and i < m)
							i += 1
						elsif(c != pattern[i] and i < m)
							fine = true
							break
						else #Ho finito il pattern
							break
						end
					end
					
					#Finisco se ho finito il pattern oppure se il match è finito in mezzo
					if(fine)
						nil 
					end			
				end
			end
			suffissi(u)
										
		end

		
# Cerco i figli di __nodo__ il cui primo carattere sia == a str[0]
		def figlio(nodo, str)
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo"
			end
			c = 0
			if(str.respond_to?(:to_str)) 
				c = str.to_str[0]
			elsif(c.respond_to?(:to_i))
				c = str.to_i
			end
			
			if(nodo.figli.nil? or nodo.figli.empty?)
				return nil
			end
			
		rv = nil
			nodo.figli.each_with_index do |f, f_i| 
				s = @dominio[f.chiave.indice][f.chiave.inizio]
					
				if(s == c)	#Ho trovato il ramo
						rv = f 
				break
				end
			end
		rv
		end

# Ritorna un array con tutti i suffissi che competono al nodo passato, nel caso
# ve ne sia soltanto uno ritorna una stringa se non ve n'è nessuno ritorna nil
		def suffissi(nodo)
			if(nodo.nil?)
				return nil
			end
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo #{nodo.class}"
			end
			
			if(nodo.is_leaf?)
				return l(nodo)
			end
			
			if(nodo.figli.respond_to?(:each))
				r_a = Array.new
				r_v = nodo.figli.collect{|f| suffissi(f)}
				r_v.each	{|rv| 
					if(rv.is_a?(Array)); r_a.concat(rv); else r_a.push(rv); end
					}

				return r_a
			end

			nil
		end
		
		
		#Restituisce la profondità (depth) del nodo
		def d(nodo) 
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo"
			end
			
			i_d = 0
			u = nodo
			while(!u.is_root?) do
				i_d += 1
				u = u.padre
			end
			
			i_d
		end
		
		
#Restituisce l'etichetta (label) del nodo
		def l(nodo) 
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo"
			end
			
			if(nodo.is_root?) 
				""
			end
			
			str = pezzo(nodo)
			dom = @dominio[nodo.chiave.indice]
			u = nodo
			before = ""
			while(!u.padre.is_root?) do
				u = u.padre
				before = pezzo(u) << before
			end
			
			before << str
		end
		
# Ricerca ricorsiva del nodo cui il pattern appartiene
		private 
		def search_int(pattern, node)
			if(node.nil?)
				nil
			end
			
			is_prefix = true
			nx_pos = pos
			
			#Se non è il nodo di root (vuoto) controllo se il nodo fa match
			# in tal caso lo ritorno
			if(!node.is_root?)
				l = pattern.length - pos
				
				#Non ho + nulla da confrontare
				if(l <= 0); nil; end
				
				ml = [l, node.chiave.lunghezza].min
				dom = @dominio[node.chiave.indice]
											[nodo.chiave.inizio, nodo.chiave.lunghezza]
			
				is_prefix = pattern[pos, ml] <= dom
				nx_pos += ml	
				#Ho trovato il nodo	
				if(is_prefix and l <= ml); node; end
					
			end
			
			
			#Visita in ampiezza del trie con radice node
			s_n = nil
			node.figli.each do |f|
				s_n = search_int(pattern, f, nx_pos)
				if(!s_n.nil?); f; end
			end
			
			#Se non mi sono fermato prima non ho match => ritorno nil
			nil
		end
		
#Aggiunge una stringa al dominio del Trie
		public
		def add(adom)
			if(!adom.respond_to?:to_str)
				raise ArgumentError, "Solo stringhe: #{adom}"
			end
			dom = adom.to_str
			if(@root.nil?)
				@root = SuffixNode.new(SuffixNodeKey.new, Array.new)
			end
			index = @dominio.size
			@dominio.push(dom)
			
			m = dom.length
			#Costruisco l'array di tutti i suffissi della stringa dom
			su_arr = to_suffix_array(dom)
			
			su_arr.each_with_index do |sfx, inizio|				
				sfxs_found = search(sfx, @root) #Controllo se esiste già
				
				if(sfxs_found.nil?) #E' un nuovo suffisso ma non so a che livello
					# i = indice del pattern 
					# j = indice del suffisso corrente
					i = inizio
					j = sfx.length
					fine = false
					u = @root
					while(!fine and i < m)
						indice = i
						v = u
						w = figlio(u, dom[i])
						if(w.nil?)
							fine = true
						else
							u = w
							str = pezzo(u)
							str.each_byte do |c|								
								if(i < m and c == dom[i])
									i += 1
									j -= 1
								elsif(c != dom[i])
									fine = true
									break
								end
							end
						end
					
					end
					
					if(fine) 
						crea_foglia(v, u, i - indice, index, i, j)
					end
				else
					#C'è già
				end
			
			end
			
			@root
		end
		
#catattere chiave
		def key_char(nodo)
			if(!nodo.is_a?(SuffixNode)) 
				raise ArgumentError, "Deve essere un nodo"
			end
			@dominio[nodo.chiave.indice][nodo.chiave.inizio]
		end

#Crea una foglia a partire dal nodo figlio
		def crea_foglia(padre, figlio, i_shift, indice, i, l)
			if(padre != figlio)
				old_l = figlio.chiave.lunghezza
				#Spezzo il trie in due
				figlio.chiave.lunghezza = i_shift
				#Creo il ramo per il pezzo esistente
				new_i = figlio.chiave.inizio + i_shift
				new_l = old_l - figlio.chiave.lunghezza
				n_k = SuffixNodeKey.new(figlio.chiave.indice, new_i, new_l)
				esist = SuffixNode.new(n_k, figlio.figli, figlio)
				
				#Collego il nuovo ramo al Trie
				figlio.figli = [esist]				
			end
			n_k	= SuffixNodeKey.new(indice, i, l)
			leaf = SuffixNode.new(n_k, nil, figlio)
			figlio.figli.push(leaf)
			leaf
		end
		
# Data una stringa crea l'array dei suffissi della stessa			
		def to_suffix_array(dom)
			ret_arr = Array.new()
			0.upto(dom.length - 1) {|i| ret_arr[i]= dom[i...dom.length]}
			ret_arr
		end
		
		def print_trie(root, d = 0) 
			if(root.nil? or !root.is_a?(SuffixNode))
				return nil
			end

			if(root.is_root?)
				printf "/"
				d = 1
			else
				0.upto d do; printf " "; end
				printf "/#{pezzo(root)}"
			end
			if(root.is_leaf?)
				printf "$\n"
			else 
				printf "\n"
				root.figli.each {|f| print_trie(f, d + root.chiave.lunghezza + 1)}
			end
		end
end

